import com.akaovi.exp.utils.Utils;

import java.util.Arrays;

/**
 * @author akaovi
 * @version 1.0
 * @description
 * @date 2022/10/10 15:07
 * @since 2022/10/10 15:07
 */
public class LessMoneyNum {
    public static void main(String[] args) {
        // 钱币面额
        int[] c = {1, 2, 5, 10, 20, 50, 100, 500};

        // 面额
        System.out.print("请输入需要凑的面额: ");
        int money = Utils.getOneInt();

        int[] dp = new int[money + 5];
        Arrays.fill(dp, money + 5);

        dp[0] = 0;

        for (int i = 1; i < dp.length; i++) {
            for (int k : c) {
                if (i - k >= 0) {
                    dp[i] = Math.min(dp[i - k] + 1, dp[i]);
                }
            }
        }

        System.out.println(dp[money] > money ? -1 : dp[money]);
    }
}
